/*
 * TestExtendedEuclid.cpp
 *
 *   Created on: 2010-3-16     
 *  Description: 实现并测试简单的“拓展欧几里得”算法，用于求乘法逆元
 *    Copyright: 2010 @ ICT Li Heyuan
 */

#include <iostream>
#include <stdexcept>
using namespace std;

long long gcd(long long a, long long b)
{
	while (b != 0)
	{
		long long r = b;
		b = a % b;
		a = r;
	}
	return a;
}

//求d^-1==1 mod f
long long extendEuclid(long long d, long long f)
{
	//vector
	long long x[3], y[3], t[3], q;

	//init
	x[0] = 1;
	x[1] = 0;
	x[2] = f;

	y[0] = 0;
	y[1] = 1;
	y[2] = d;
	while (true)
	{
		if (y[2] == 0)//step 2
		{
			throw runtime_error("no modInverse can be caculated");
		}

		if (y[2] == 1)//step 3
		{
			//如果是负数，需要进行拓展，
			//设y[1]为特解y0则，通解为y=(y0+f*t)/gcd(a,n),t为任意整数
			if (y[1] <= 0)
			{
				cout << "check:" << endl;
				long long t = (-y[1] / f) + 1;
				return (y[1] + f * t) / gcd(d, f);
			}
			else
			{
				return y[1];
			}
		}

		q = x[2] / y[2];//step 4

		t[0] = x[0] - q * y[0];//step 5
		t[1] = x[1] - q * y[1];
		t[2] = x[2] % y[2];

		x[0] = y[0];//step 6
		x[1] = y[1];
		x[2] = y[2];

		y[0] = t[0];//step 7
		y[1] = t[1];
		y[2] = t[2];
	}
}

void extend_gcd(long long a, long long b, long long& x, long long& y)
{
	if (!b)
	{
		x = 1, y = 0;
		return;
	}
	else
	{
		extend_gcd(b, a % b, x, y);
		int t = x;
		x = y;
		y = t - (a / b) * y;
	}
}
/*

int main()
{
	long long d = 1, f = 80, result, cnt = 0;
	d = 7;
	for (long long i = 0; i < f; i++)
	{
		try
		{
			result = extendEuclid(i, f);
			cout << i << " * " << result << " mod " << f << "=1" << endl;

		} catch (...)
		{

		}
	}
	cout << "total:" << cnt << endl;
	cout << (-1 % 37) << endl;
	return 0;
}
*/
